'''
Created on 2010-3-3

@author: Administrator
'''
import sys
from jolly.datastructures.Object import Object
from jolly.datastructures.Tree import Tree
from jolly.datastructures.Array import Array
from jolly.datastructures.Exception import *

class NaryTree(Tree):
    '''
    N-ary tree implemented using an array of._subtrees.
    '''


    def __init__(self, *args):
        '''
        (NaryTree, int [, Object]) -> None
        Constructs an N-ary tree.
        '''
        super(NaryTree, self).__init__()
        if len(args)==1:
            self._degree=args[0]
            self._key=None
            self._subtree=None
        elif len(args)==2:
            self._degree=args[0]
            self._key=args[1]
            self._subtree=Array(self._degree)
            for i in xrange(self._degree):
                self._subtree[i]=NaryTree(self._degree)
    
    def purge(self):
        '''
        (NaryTree) -> None
        Purges this N-ary tree.
        '''
        self._key=None
        self._subtree=None
    
    def getDegree(self):
        '''
        (NaryTree) -> int
        Returns the degree of this N-ary tree.
        '''
        if self.isEmpty:
            return 0
        else:
            return self._degree
    
    def getIsLeaf(self):
        '''
        (NaryTree) -> bool
        Returns true if this N-ary tree is a leaf.
        '''
        if self.isEmpty:
            return False
        for i in xrange(self._degree):
            if not self._subtree[i].isEmpty:
                return False
        return True
    
    def getIsEmpty(self):
        '''
        (NaryTree) -> bool
        Returns true if this N-ary tree is empty.
        '''
        return self._key is None

    def getKey(self):
        '''
        (NaryTree) -> Object
        Returns the._key of this N-ary tree node.
        '''
        if self.isEmpty:
            raise StateError
        return self._key
    
    def attachKey(self, obj):
        '''
        (NaryTree, Object) -> None
        Makes the given object the._key of this N-ary tree node.
        '''
        if not self.isEmpty:
            raise StateError
        self._key=obj
        self._subtree=Array(self._degree)
        for i in xrange(self._degree):
            self._subtree[i]=NaryTree(self._degree)
    
    def detachKey(self):
        '''
        (NaryTree) -> Object
        Detaches and returns the._key of this N-ary tree node.
        '''
        if not isLeaf:
            raise StateError
        result=self._key
        self._key=None
        self._subtree=None
        return result
    
    def getSubtree(self, i):
        '''
        (NaryTree, int) -> NaryTree
        Returns the specified._subtree of this N-ary tree.
        '''
        if self.isEmpty:
            raise StateError
        return self._subtree[i]
    
    def attachSubtree(self, i, t):
        '''
        (NaryTree, int, NaryTree) -> None
        Attaches the given tree as the specified._subtree of this N-ary tree.
        '''
        if self.isEmpty or not self._subtree[i].isEmpty:
            raise StateError
        self._subtree[i]=t
    
    def detachSubtree(self, i):
        '''
        (NaryTree, int) -> NaryTree
        Detaches and returns the specified._subtree of this N-ary tree.
        '''
        if self.isEmpty:
            raise StateError
        result=self._subtree[i]
        self._subtree[i]=NaryTree(degree)
        return result
    
    def _compareTo(self, obj):
        '''
        (NaryTree, NaryTree) -> int

        Compares this N-ary tree with the given N-ary tree.
        '''
        assert isinstance(self, obj.__class__)
        raise NotImplementedError
    
    @staticmethod
    def main(*argv):
        'NaryTree test program.'
        print NaryTree.main.__doc__
        nt = NaryTree(3, 1)
        nt.attachSubtree(0, NaryTree(3,2))
        nt.attachSubtree(1, NaryTree(3,3))
        nt.attachSubtree(2, NaryTree(3,4))
        nt.getSubtree(0).attachSubtree(0, NaryTree(3, 5))
        nt.getSubtree(2).attachSubtree(1, NaryTree(3, 6))
        Tree.test(nt)
        return 0

if __name__ == "__main__":
    sys.exit(NaryTree.main(*sys.argv))